package com.example.chinesenation.Utils;

import com.alibaba.druid.sql.visitor.functions.Char;
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnel;
import com.google.common.hash.Funnels;
import com.sun.org.apache.xpath.internal.operations.Bool;
import io.swagger.models.auth.In;
import javafx.util.Pair;
import org.mockito.invocation.Invocation;
import org.springframework.util.StringUtils;
import sun.misc.ObjectInputFilter;

import java.lang.reflect.InvocationHandler;
import java.util.*;
import java.util.concurrent.atomic.AtomicBoolean;

/**
 * @author sakuraFallingDown
 * @version 1.0
 * @date 2021/2/1 0:59
 */
public class TextTools{//处理过长文本

    private final static int length = 50;//最长文本数

    public static String handlerLongString(String args) {
        args = StringUtils.trimAllWhitespace(args);
        if (args.length() > length) {
            args = args.substring(0, length);
            args += "...[查看详情]";
        } else {
            args += "[查看详情]";
        }

        
        return args;
    }

    public static void main(String[] args) {
        /*
        int nums[]=new int[]{1};
        int start=0,end=nums.length-1;
        while(start< nums.length&&nums[start]==0) start++;
        while(end>=0&&nums[end]==2) end--;
        for(int i=start;i<=end;){
            if(nums[i]==0){
                nums[i]=nums[start];
                nums[start]=0;
                start++;
                i++;
            }else if(nums[i]==1){
                i++;
                continue;
            }else if(nums[i]==2){
                nums[i]=nums[end];
                nums[end]=2;
                end--;
            }
        }
        System.out.println(Arrays.toString(nums));

         */
        String words[] = new String[]{"hello", "leetcode"};
        String order = "hlabcdefgijkmnopqrstuvwxyz";
        //System.out.println(isAlienSorted(words,order));
        //system.out.println(Arrays.toString(printNumbers(5)));
        String[] w = {"aaaa", "asas", "able", "ability", "actt", "actor", "access"};
        String p[] = {"aboveyz", "abrodyz", "abslute", "absoryz", "actresz", "gaswxyz"};
        //System.out.println(findNumOfValidWords(w,p));
        //System.out.println(sortString("aaaabbbcccccc"));
        int arr[]=new int[]{1,3,5,7,2,4,6,8,1,2,3,4,5,1,2,1};
        int k=4;
        //System.out.println(Arrays.toString(smallestK(arr,k)));
        //System.out.println(minCut("aab"));
        //System.out.println(calculate("1*2-3/4+5*6-7*8+9/10"));
        //System.out.println(Arrays.toString(maxSlidingWindow(new int[]{1, 3, -1, -3, 5, 3, 6, 7}, 3)));
        //System.out.println(findMaxForm(new String[]{"10","0001","111001","1","0"},5,3));
    }
    public int evalRPN(String[] tokens) {
        int n=tokens.length;
        int num=0;
        if(n==0) return num;
        Stack<Integer> stack=new Stack<>();
        for (String token : tokens) {
            if(token.equals("+")){
                int num1=stack.pop();
                int num2=stack.pop();
                stack.push(num1+num2);

            }else  if(token.equals("-")){
                int num1=stack.pop();
                int num2=stack.pop();
                stack.push(num2-num1);
            }else if(token.equals("*")){
                int num1=stack.pop();
                int num2=stack.pop();
                stack.push(num1*num2);
            }else if(token.equals("/")){
                int num1=stack.pop();
                int num2=stack.pop();
                stack.push(num2/num1);
            }else{
                stack.push(Integer.parseInt(token));
            }
        }
        return stack.pop();
    }
    int xi[]=new int[]{-1,1,0,0};
    int yi[]=new int[]{0,0,-1,1};

    public boolean exist(char[][] board, String word) {
        if(word.length()==0) return true;
        boolean flag=false;
        int n=board.length;
        int m=board[0].length;
        int x[]=new int[]{1,0,-1,0};
        int y[]=new int[]{0,1,0,-1};//分别表示下右上左
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(board[i][j]==word.charAt(0)){
                    flag=dfs(board,word,i,j,0);
                    if(flag){
                        return true;
                    }
                }
            }
        }
        return flag;
    }
    
    public boolean dfs(char[][]board,String word,int x,int y,int index){
        if(index>word.length()) return true;
        char c=word.charAt(index);
        boolean flag=false;
        if(x>=0&&y>=0&&x<board.length&&y<board[0].length&&board[x][y]==c) {
            board[x][y]='\0';
            for (int i = 0; i < 4; i++) {
                flag= (flag ||dfs(board, word, x + xi[i], y + yi[i], index + 1));
            }
            board[x][y]=c;
            return flag;
        }else{
            return false;
        }
    }
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode head1=new ListNode();
        ListNode head2=new ListNode();
        head1.next=headA;
        head2.next=headB;
        ListNode p=head1;
        ListNode q=head2;
        int lengthA=0;
        int lengthB=0;
        while(p!=null){
            lengthA++;
            p=p.next;
        }
        while(q!=null){
            lengthB++;
            q=q.next;
        }
        p=head1;
        q=head2;
        if(lengthA>lengthB){
            while(lengthA!=lengthB){
                p=p.next;
                lengthA--;
            }
        }else{
            while(lengthA!=lengthB){
                q=q.next;
                lengthB--;
            }
        }
        while(p.next!=null&&p.next!=q.next){
            p=p.next;
            q=q.next;
        }
        return p;
    }
    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null) return null;
        if(p==q){
            return p;
        }
        Stack<TreeNode> stack=new Stack<>();
        Stack<TreeNode> stack1=new Stack<>();
        Stack<TreeNode> stack2=new Stack<>();
        HashMap<TreeNode,Boolean> map=new HashMap<>();
        TreeNode node=root;
        while(node!=null||!stack.isEmpty()){
            while(node!=null){
                stack.push(node);
                node=node.left;
                map.put(node,true);
            }
            TreeNode treeNode=stack.peek();
            if(map.containsKey(treeNode)){
                map.remove(treeNode);
                node=treeNode.right;
            }else{
                if(treeNode==p){
                    stack1.addAll(stack);
                }
                if(treeNode==q){
                    stack2.addAll(stack);
                }
                stack.pop();
                if(stack1.size()!=0&&stack2.size()!=0) break;
            }
        }
        node=root;
        int l1=stack1.size();
        int l2=stack2.size();
        if(l1>l2){
            while(stack1.size()!=l2){
                stack1.pop();
            }
        }else if(l2>l1){
            while(stack2.size()!=l1){
                stack2.pop();
            }
        }
        while(stack1.size()!=0){
           if((node=stack1.pop())==stack2.pop()){
               return node;
           }
        }
        return node;
    }
    public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if(left==right) return head;
        ListNode l=new ListNode();
        l.next=head;
        int count=1;
        ListNode start=l;
        while(count<left){
            count++;
            start=start.next;
        }
        ListNode p=start.next;
        ListNode start1=start.next;
        ListNode end1;
        ListNode end;
        if(p==null) return l.next;
        ListNode q=p.next;
        ListNode k=q;
        while(q!=null&&left<right){
            left++;
            k=q.next;
            q.next=p;
            p=q;
            q=k;
        }
        start.next=q;
        start1.next=k;
        return l.next;
    }

    public static int findMaxForm(String[] strs, int m, int n) {
        int length=strs.length;
        int [][]nums=new int[length][2];
        for(int i=0;i<length;i++){
            String str=strs[i];
            int zero=0,one=0;
            for(int j=0;j<str.length();j++){
                if(str.charAt(j)=='0') zero++;
                else one++;
            }
            nums[i][0]=zero;
            nums[i][1]=one;
        }
        return max(nums,m,n,0);
    }
    public static int max(int [][]nums,int m,int n,int i){
        if(i==nums.length) return 0;
        if(nums[i][0]<m&&nums[i][1]<n){
            return Math.max(max(nums,m-nums[i][0],n-nums[i][1],i+1),max(nums,m,n,i+1))+1;
        }
        return max(nums,m,n,i+1);
    }

    public int numDistinct(String s, String t) {
        int m=s.length();
        int n=t.length();
        if(n>m) return 0;
        if(n==0) return 1;
        int[][] dp =new int[m+1][n+1];
        for(int i=0;i<m;i++){
            dp[i][n-1]=1;
        }
        for(int i=m-2;i>=0;i--){
            for(int j=n-2;j>=0;j--){
                if(s.charAt(i)==t.charAt(j)){
                    dp[i][j]=dp[i+1][j+1]+dp[i+1][j];
                }else{
                    dp[i][j]=dp[i+1][j];
                }
            }
        }
        return dp[0][0];
    }

    public boolean isStraight(int[] nums) {
        int count=0;
        Arrays.sort(nums);
        for(int i=0;i<nums.length;){
            if(nums[i]==0){
                count++;
                i++;
            }else{
                if(i>0&&nums[i-1]+1!=nums[i]) {
                    if(count>0) {
                        count --;
                        nums[i-1]++;
                    }else{
                        return false;
                    }
                }else{
                    i++;
                }
            }
        }
        return true;
    }
    public static int[] maxSlidingWindow(int[] nums, int k) {
        int[] num=new int[nums.length-k+1];
        TreeMap<Integer,Integer> map=new TreeMap<>();
        for(int i=0;i<k;i++){
            map.put(nums[i],map.getOrDefault(nums[i],0)+1);
        }
        num[0]=map.lastKey();
        for(int i=k;i<nums.length;i++){
            map.put(nums[i],map.getOrDefault(nums[i],0)+1);
            int count=map.get(nums[i-k]);
            if(count==1){
                map.remove(nums[i-k]);
            }else{
                map.put(nums[i-k],count-1);
            }
            num[i-k+1]=map.lastKey();
        }
        return num;
    }
    public int[][] generateMatrix(int n) {
        if(n==0) return null;
        int [][]matrix=new int[n][n];
        int k=0;
        int x=0,y=0;
        int times=0;
        while(k<n*n){
            while(k<n*n&&y<n-times) matrix[x][y++]=++k;
            y--;
            x++;
            while(k<n*n&&x<n-times) matrix[x++][y]=++k;
            y--;
            x--;
            while(k<n*n&&y>=times) matrix[x][y--]=++k;
            y++;
            x--;
            while(k<n*n&&x>times) matrix[x--][y]=++k;
            y++;
            x++;
            times++;
        }
        return matrix;
    }
    public List<Integer> spiralOrder(int[][] matrix) {
        int row=matrix.length;
        if(row==0) return null;
        int col=matrix[0].length;
        if(col==0) return null;
        List<Integer> list=new ArrayList<>();
        int x=0,y=0;
        int times=0;
        while(list.size()<row*col){
            while(list.size()<row*col&&y<row-times)  list.add(matrix[x][y++]);
            y--;
            x++;
            while(list.size()<row*col&&x<row-times)  list.add(matrix[x++][y]);
            x--;
            y--;
            while(list.size()<row*col&&y>=times)  list.add(matrix[x][y--]);
            x--;
            y++;
            while(list.size()<row*col&&x>times)  list.add(matrix[x--][y]);
            x++;
            y++;
        }
        return list;
    }

    public boolean isValidSerialization(String preorder) {
        int n=preorder.length();
        if(n==0||n==1) return true;
        int count=1;
        String[] split = preorder.split(",");
        for (String s : split) {
            if(s.equals("#")){
                count--;
            }else{
                count++;
            }
        }
        return count==0;
    }
    public static int calculate(String s) {
        Stack<Integer> stack=new Stack<>();
        Stack<Character> stack1=new Stack<>();
        int n=s.length();
        if(n==0) return 0;
        if(s.charAt(0)=='-') stack.push(0);
        for(int i=0;i<n;i++){
            int num=0;
            if(s.charAt(i)>='0'&&s.charAt(i)<='9') {
                for (; i<n&&s.charAt(i) >= '0' && s.charAt(i) <= '9'; i++) {
                    num = num * 10 + s.charAt(i) - '0';
                }
                stack.push(num);
            }
            if(i<n&&s.charAt(i)=='*'){
                if(!stack1.empty()){
                    if(stack1.peek()!='+'&&stack1.peek()!='-'){
                        c(stack,stack1);
                    }
                }
                stack1.push('*');
            }else if(i<n&&s.charAt(i)=='+'){
                while(!stack1.empty()){
                    c(stack,stack1);
                }
                stack1.push('+');
            }else if(i<n&&s.charAt(i)=='-'){
                while(!stack1.empty()){
                    c(stack,stack1);
                }
                stack1.push('-');
            }else if(i<n&&s.charAt(i)=='/'){
                if(!stack1.empty()){
                    if(stack1.peek()!='+'&&stack1.peek()!='-'){
                        c(stack,stack1);
                    }
                }
                stack1.push('/');
            }
        }
        if(!stack1.empty()){
            c(stack,stack1);
        }
        return stack.pop();
    }
    private static void c(Stack<Integer> stack,Stack<Character> stack1){
        Character c=stack1.pop();
        if (c == '+') {
            Integer num1 = stack.pop();
            Integer num2 = stack.pop();
            stack.push(num1+num2);
        }else if(c=='-'){
            Integer num1 = stack.pop();
            Integer num2 = stack.pop();
            stack.push(num2-num1);
        }else if(c=='*'){
            Integer num1 = stack.pop();
            Integer num2 = stack.pop();
            stack.push(num2*num1);
        }else if(c=='/'){
            Integer num1 = stack.pop();
            Integer num2 = stack.pop();
            stack.push(num2/num1);
        }
    }

    public String removeDuplicates(String s) {
        if(s==null) return null;
        int n=s.length();
        if(n==0||n==1) return s;
        StringBuffer sb=new StringBuffer();
        sb.append('0');
        int top=0;
        for(int i=0;i<n;i++){
            if(s.charAt(i)==sb.charAt(top)){
                sb.deleteCharAt(top);
                top--;
            }else{
                sb.append(s.charAt(i));
                top++;
            }
        }

        return sb.substring(1);
    }

    public int lengthOfLongestSubstring(String s) {
        int n=s.length();
        if(n<=0) return 0;

        HashMap<Character,Integer> map=new HashMap<>();
        int start=0,end=0;
        int max=0;
        for( ;end<n;end++){
            if(map.containsKey(s.charAt(end))){
                max=Math.max(end-start,max);
                while(map.containsKey(s.charAt(end))){
                    map.remove(s.charAt(start));
                    start++;
                }
            }else{
                map.put(s.charAt(end),0);
            }
        }
        return max;
    }
    public   static int minCut(String s) {
        Boolean[][] flag;
        int n;
        n=s.length();
        flag=new Boolean[n][n];
        for(int i=0;i<n;i++){
            Arrays.fill(flag[i],true);
        }
        for(int i=n-1;i>=0;i++){
            for(int j=i+1;j<n;j++){
                flag[i][j]=(flag[i+1][j-1])&&(s.charAt(i)==s.charAt(j));
            }
        }
        int f[]=new int[n];
        Arrays.fill(f,n);
        for(int i=0;i<n;i++){
            if(flag[0][i]){
                f[i]=1;
            }else{
                for(int j=1;j<i;j++){
                    if(flag[j][i]){
                        f[i]=Math.min(f[i],f[j]+1);
                    }
                }
            }
        }
        return f[n-1];
    }
    public  static int[] smallestK(int[] arr, int k) {
        if(k>=arr.length) return arr;
        int nums[]=new int[k];
        if(arr.length==0) return nums;
        sortQuick(arr,0,arr.length-1,k);
        for(int i=0;i<k;i++){
            nums[i]=arr[i];
        }
        return nums;
    }
    private static void sortQuick(int []arr,int start,int end,int k){
        if(k==0) return ;
        if(end-start+1<=k){
            return ;
        }

        int index1=start,index2=end;
        int num=arr[start];
        while(index1<index2){
            while(index1<index2&&arr[index2]>num) index2--;

            if(index1<index2) {
                arr[index1] = arr[index2];
                index1++;
            }

            while(index1<index2&&arr[index1]<num) index1++;
            if(index1<index2) {
                arr[index2] = arr[index1];
                index2--;
            }

        }
        arr[index1]=num;
        if(index1-start+1>k){
            sortQuick(arr,start,index1-1,k);
        }else if(index1-start+1<k){
            sortQuick(arr,index1+1,end,k-index1+start-1);
        }
        return ;
    }

    public int maxValue(int[][] grid) {
        int row=grid.length;
        if(row==0) return 0;
        int col=grid[0].length;
        if(col==0) return 0;
        int [][]price=new int[row+1][col+1];
        for(int i=1;i<row+1;i++){
            for(int j=1;j<col+1;j++){
                price[i][j]=Math.max(price[i-1][j],price[i][j-1])+grid[i-1][j-1];
            }
        }
        return price[row][col];
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null) return null;
        if(p==q){
            return p;
        }
        Stack<TreeNode> stack=new Stack<>();
        List<TreeNode> list1=new ArrayList<>();
        List<TreeNode> list2=new ArrayList<>();
        boolean flag1=true,flag2=true;
        HashMap<TreeNode, Boolean> map=new HashMap<>();
        TreeNode peek = root;
        while(!stack.empty()){
            while(peek!=null){
                stack.push(peek.left);
                peek=peek.left;

            }
            if(!map.containsKey(peek)) {
                peek=peek.right;
                if(peek!=null) {
                    map.put(peek, true);
                }
            }else{
                TreeNode pop = stack.peek();
                if(pop==p){
                    flag1=false;
                }
                if(pop==q){
                    flag2=false;
                }
                stack.pop();
            }
        }
        for(int i=0;i<list1.size()-1&&i<list2.size()-1;i++){
            if(list1.get(i+1)!=list2.get(i+1)){
                return list1.get(i);
            }
        }
        return null;
    }
    public static String replaceSpace(String s) {
        return s.replaceAll(" ", "%20");
    }



    public static int maxEnvelopes(int[][] envelopes) {
        if(envelopes.length==0) return 0;
        if(envelopes.length==1) return 1;
        Arrays.sort(envelopes, (o1, o2) -> {
            if(o1[0]>o2[0]) return 1;
            else if(o1[0]<o2[0]) return -1;
            else {
                if(o1[1]>o2[1]) return 1;
                else if(o1[1]<o2[1]) return -1;
            }
            return 0;
        });
        int max=0;
        int depth[]=new int[envelopes.length];
        Arrays.fill(depth,1);
        for(int i=1;i<depth.length;i++){
            for(int j=0;j<i;j++){
                if(envelopes[j][1]<envelopes[i][1]){
                    depth[i]=Math.max(depth[i],depth[j]+1);
                }
            }
            max=Math.max(max,depth[i]);
        }
        return max;




    }


    public static int[] countBits(int num) {
        int bits[]=new int[num+1];
        bits[0]=0;
        if(num==1) bits[1]=1;
        if(num>=2) {
            bits[1]=1;
            bits[2] = 2;
        }
        int size=2;
        int count=0;
        for(int i=2;i<num+1;i++){
            if(count==size){
                count=0;
                size*=2;
            }
            bits[i]=bits[i-size]+1;
            count++;
        }
        return bits;
    }

    public static String sortString(String s) {
        StringBuilder sb=new StringBuilder();
        TreeMap<Character,Integer> treeMap=new TreeMap<>();
        for(int i=0;i<s.length();i++){
            treeMap.put(s.charAt(i),treeMap.getOrDefault(s.charAt(i),0)+1);
        }
        while(treeMap.size()!=0){
            for(Map.Entry<Character,Integer> entry:treeMap.entrySet()){
                sb.append(entry.getKey());
                Integer integer = entry.getValue();
                if(integer==1){
                    treeMap.remove(entry.getKey());
                } else{
                    treeMap.put(entry.getKey(),integer-1);
                }
            }
        }
        return sb.toString();
    }
    public static int longestSubstring(String s, int k) {

        return getLength(s,k,0,s.length());
    }

    public static int getLength(String s, int k,int start,int end){
        if(end-start<k) return 0;

        HashMap<Character,Integer> map=new HashMap<>();
        for(int i=start;i<end;i++){
            map.put(s.charAt(i),map.getOrDefault(s.charAt(i),0)+1);
        }
        for(int i=start;i<end;i++){
            if(map.get(s.charAt(i))<k){
                return Math.max(getLength(s,k,start,i),getLength(s,k,i+1,end));
            }
        }
        return end-start;

    }
    
    public static List<Integer> findNumOfValidWords(String[] words, String[] puzzles) {
        List<Integer> list=new ArrayList<>();
        for(int i=0;i< puzzles.length;i++) {
            list.add(0);
        }
        List<HashMap<Character,Integer>> puzzlesMap=new ArrayList<>();
        List<HashMap<Character,Integer>> wordMap=new ArrayList<>();
        for(String str:puzzles) {
            HashMap<Character,Integer> map=new HashMap<>();
            for(int i=0;i<str.length();i++){
                if(!map.containsKey(str.charAt(i))) {
                    map.put(str.charAt(i), 0);
                }
            }
            puzzlesMap.add(map);
        }
        for(String str:words) {
            HashMap<Character,Integer> map=new HashMap<>();
            for(int i=0;i<str.length();i++){
                if(!map.containsKey(str.charAt(i))) {
                    map.put(str.charAt(i), 0);
                }
            }
            wordMap.add(map);
        }

        for(HashMap<Character,Integer> word:wordMap){

            for(int i=0;i<puzzlesMap.size();i++){
                boolean flag= true;
                boolean isFirst=false;
                HashMap<Character,Integer> map=puzzlesMap.get(i);
                for(Character c:word.keySet()){
                    if(!map.containsKey(c)){
                        flag=false;
                        break;
                    }
                    if((!isFirst)&&c==puzzles[i].charAt(0)){
                        isFirst=true;
                    }
                }
                if(flag&&isFirst){
                    int count=list.get(i);
                    list.set(i,count+1);
                }
            }
        }
        return list;
    }

    public static StringBuilder[] printNumbers(int n) {
        StringBuilder []nums=new StringBuilder[(int)Math.pow(10,n)-1];

        for(int i=n-1;i>=0;i--){
            for(int j=0;j<nums.length;j++){
                nums[j].append(j/(int)Math.pow(10,i));
            }
        }
        return nums;
    }

    public int numPermsDISequence(String S) {
        int mod=1_000_000_007;
        int count=0;
        int N=S.length();
        int dp[][]=new int[N+1][N+1];
        Arrays.fill(dp[0],1);
        for(int i=1;i<N+1;i++){
            for(int j=0;j<N+1;j++){
                if(S.charAt(i-1)=='D'){
                    for (int k = j; k < i; k++) {
                        dp[i][j] += dp[i-1][k];
                        dp[i][j] %= mod;
                    }
                }else if(S.charAt(i-1)=='I'){
                    for (int k = 0; k <j; k++) {
                        dp[i][j] += dp[i-1][k];//上一行的元素
                        dp[i][j] %= mod;
                    }
                }
            }
        }
        for (int i = 0; i < dp[N].length; i++) {
            count+=dp[N][i];
            count%=mod;
        }
        return count;
    }
    class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }
    public TreeNode mirrorTree(TreeNode root) {
        if(root==null) return root;
        Stack<TreeNode> stack=new Stack<>();
        stack.push(root);
        while (!stack.empty()){
            TreeNode pop = stack.pop();
            TreeNode t=pop.left;
            pop.left=pop.right;
            pop.right=t;
            if(pop.left!=null){
                stack.push(pop.left);
            }
            if(pop.right!=null){
                stack.push(pop.right);
            }
        }
        return root;
    }
    public int maxDepth(TreeNode root) {
        if(root==null) return 0;
        int depth=1;
        int max=1;
        Stack<Pair<TreeNode,Integer>> stack=new Stack<>();
        stack.push(new Pair<>(root,1));
        while (!stack.empty()){
            Pair<TreeNode, Integer> pop = stack.pop();
            TreeNode key = pop.getKey();
            Integer value = pop.getValue();
            max=Math.max(max,value);
            if(key.left!=null){
                stack.push(new Pair<>(key.left,value+1));
            }
            if(key.right!=null){
                stack.push(new Pair<>(key.right,value+1));
            }

        }
        return max;
    }
    public static int[] missingTwo(int[] nums) {
        int num[]=new int[2];
        double a=0,b=0;
        int sum=(1+nums.length+2)*(nums.length+2)/2;
        int sumNums=0;
        int sum2=0;
        int sum2Nums=0;
        for(int i=0;i<nums.length;i++){
            sumNums+=nums[i];
            sum2Nums+=nums[i]*nums[i];
            sum2+=(i+1)*(i+1);
        }
        sum2+=(nums.length+1)*(nums.length+1)+(nums.length+2)*(nums.length+2);
        int ab=sum-sumNums;//a+b之和
        int ab2=sum2-sum2Nums;//a2+b2平方之和
        /**
         * a2+b2=num1;
         * a+b=num2;
         * b=num2-a;
         * a2+a2-2*num2*a+(num2)2-num1=0
         *
         * 在一元二次方程中
         * a=2,b=-2*num2,c=(num2)2-num1;
         *
         * 即
         * 2,-2*ab,ab*ab-ab2
         *
         */
        double b24ac=Math.sqrt(4*ab*ab-4*2*(ab*ab-ab2));
        a=((2*ab)+b24ac)/4;
        if(a>ab||a<0){
            a=((2*ab)-b24ac)/4;
        }
        b=ab-a;
        num[0]=(int)a;
        num[1]=(int)b;
        return num;
    }
    public static boolean isAlienSorted(String[] words, String order) {
        for(int i=1;i<words.length;i++){
            String first=words[i-1];
            String second=words[i];
            boolean flag=false;
            for(int j=0;j<first.length()&&j<second.length();j++){
                if(order.indexOf(first.charAt(j))>order.indexOf(second.charAt(j))){
                    return false;
                }else if(order.indexOf(first.charAt(j))<order.indexOf(second.charAt(j))){
                    flag=true;
                    break;
                }
            }
            if(!flag){
                if (first.length() > second.length()) {
                    return false;
                }

            }
        }

        return true;
    }


    public static int[][] flipAndInvertImage(int[][] A) {
        for(int i=0;i<A.length;i++) {
            if(A[0].length%2!=0){
                A[i][A[0].length/2]=1-A[i][A[0].length/2];
            }
            for (int j = 0; j < A[0].length / 2; j++) {
                if(A[i][j]==A[i][A[0].length-j-1]){
                    A[i][j]=1-A[i][j];
                    A[i][A[0].length-j-1]=1-A[i][A[0].length-j-1];
                }
            }
        }
        return A;

    }
    public static int maxSatisfied(int[] customers, int[] grumpy, int X) {
        int length=customers.length;
        int max=0;

        for(int i=0;i<length;i++){
            if(i<X){
                max+=customers[i];
            }else {
                max += grumpy[i] == 0 ? customers[i] : 0;
            }
        }
        int end=X;
        int count=max;
        for(int i=1;i<length;i++){
            count=count-(grumpy[i-1]==1?customers[i-1]:0);
            if(end>length-1){
                break;
            }else {
                count=count+(grumpy[end] == 1 ? customers[end] : 0);
                end++;
            }
            max=Math.max(max,count);
        }
        return max;
    }
    public static int videoStitching(int[][] clips, int T) {
        HashMap<Integer,Integer> map=new HashMap<>();
        for(int i=0;i<clips.length;i++){
            int value = map.getOrDefault(clips[i][0], 0);
            if(clips[i][1]>value) {
                map.put(clips[i][0], clips[i][1]);
            }
        }
        int firstindex=0;
        int count=0;
        int lastindex=map.get(firstindex);
        while(lastindex<T){
            int max=0;
            int index=0;
            for(int j=lastindex;j>firstindex;j--) {
                if(map.containsKey(j)) {
                    if(max<map.get(j)){
                        max=map.get(j);
                        index=j;
                    }
                }
            }
            if(max==0) return -1;
            lastindex=max;
            firstindex=index;
            count++;
        }
        return count+1;
    }
}
